package leetcode;
import java.util.*;
/**
 * 40.组合总和Ⅱ
 * 给定一个候选人编号的集合candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
 * candidates中的每个数字在每个组合中只能使用一次。
 * 注意：解集不能包含重复的组合
 *
 * 输入: candidates =[10,1,2,7,6,1,5], target =8,
 * 输出: [[1,1,6],[1,2,5],[1,7],[2,6]]
 *
 * 输入: candidates = [2,5,2,1,2], target = 5,
 * 输出: [[1,2,2],[5]]
 */
public class Num_40 {
    List<Integer> inner = new ArrayList<>();
    List<List<Integer>> outter = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates, target, 0, 0);
        return outter;
    }

    private void dfs(int[] candidates, int target, int count, int startIndex) {
        //边界条件
        if(count > target){
            return;
        }else if(count == target){
            outter.add(new ArrayList<>(inner));
            return;
        }

        //在该层节点中需要去重
        Set<Integer> set = new HashSet<>();
        for(int i = startIndex; i < candidates.length; i++){
            //检验该节点的值在该层有没有用过
            if(set.add(candidates[i])){
                inner.add(candidates[i]);
                dfs(candidates, target, count + candidates[i], i + 1);
                inner.remove(inner.size() - 1);
            }
        }
    }
}
